import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192
class FastIO(IOBase):
newlines = 0
def __init__(self, file):
self._fd = file.fileno()
self.buffer = BytesIO()
self.writable = "x" in file.mode or "r" not in file.mode
self.write = self.buffer.write if self.writable else None
def read(self):
while True:
b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
if not b:
break
ptr = self.buffer.tell()
self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
self.newlines = 0
return self.buffer.read()
def readline(self):
while self.newlines == 0:
b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
self.newlines = b.count(b"\n") + (not b)
ptr = self.buffer.tell()
self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
self.newlines -= 1
return self.buffer.readline()
def flush(self):
if self.writable:
os.write(self._fd, self.buffer.getvalue())
self.buffer.truncate(0), self.buffer.seek(0)
class IOWrapper(IOBase):
def __init__(self, file):
self.buffer = FastIO(file)
self.flush = self.buffer.flush
self.writable = self.buffer.writable
self.write = lambda s: self.buffer.write(s.encode("ascii"))
self.read = lambda: self.buffer.read().decode("ascii")
self.readline = lambda: self.buffer.readline().decode("ascii")
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")
import sys
from sys import stdin
from collections import deque
n,k = map(int,input().split())
tmpS = [ [] for i in range(10**3)]
exist = [False] * 26
for loop in range(n):
p = int(stdin.readline())
for i in range(k):
s = input()
tmpS[p].append(s)
for c in s:
exist[ord(c) - 97] = True
S = []
for i in range(10**3):
for s in tmpS[i]:
S.append(s)
lis = [ set() for i in range(26) ]
inlis = [0] * 26
for i in range(len(S)-1):
for j in range(min(len(S[i]),len(S[i+1]))):
if S[i][j] != S[i+1][j]:
lc = ord(S[i][j]) - 97
rc = ord(S[i+1][j]) - 97
if rc not in lis[lc]:
lis[lc].add(rc)
inlis[rc] += 1
break
else:
if len(S[i]) > len(S[i+1]):
print ("IMPOSSIBLE")
sys.exit()
q = deque([])
for i in range(26):
if exist[i] and inlis[i] == 0:
q.append(i)
ans = []
alp = "abcdefghijklmnopqrstuvwxyz"
while q:
v = q.popleft()
ans.append(alp[v])
for nex in lis[v]:
inlis[nex] -= 1
if inlis[nex] == 0:
q.append(nex)
if sum(inlis) == 0:
print ("".join(ans))
else:
print ("IMPOSSIBLE")
#include <bits/stdc++.h>
#define FOR(i,a,b) for(register int i=(a);i<(b);++i)
#define ROF(i,a,b) for(register int i=(a);i>=(b);--i)
#define pi pair<int,int>
#define mk(a,b) make_pair(a,b)
#define fi first
#define se second
#define ls(x) ch[x][0]
#define rs(x) ch[x][1]
#define xs(x) (ch[fa[x]][1]==x)
using namespace std;
typedef long long ll;
typedef double db;
typedef long double ldb;
typedef unsigned int ui;
typedef unsigned long long ul;
typedef long long ll;
typedef int n_;
const int maxn = 1005;
const int maxm = 500005;
const int maxlog = 63;
const int inf = 2147483647;
const double eps = 1e-9;
const double E = 2.718281828459;
const double PI = 3.1415926576;
const long long INF = 9223372036854775807ll;
inline ll qpow(ll a,ll b,ll c){register ll ans=1;while(b){if(b&1)ans=ans*a%c;a=a*a%c;b>>=1;}return ans;}
const int mod = 1e9+7;int inv6=qpow(6,mod-2,mod);
inline void dec(n_ &x,n_ y){x-=y,x<0&&(x+=mod);}
inline void add(n_ &x,n_ y){x+=y,x>=mod&&(x-=mod);}
inline n_ sum(n_ x,n_ y){return x+y<mod?x+y:x+y-mod;}
inline n_ sub(n_ x,n_ y){return x-y<0?x-y+mod:x-y;}
inline n_ sqr(n_ x){return 1ll*x*x%mod;}
inline n_ sm1(n_ x){return (1ll*x*(x+1)>>1)%mod;}
inline n_ sm2(n_ x){return 1ll*x*(x+1)%mod*(2*x+1)%mod*inv6%mod;}
inline n_ sm3(n_ x){return 1ll*sqr(x)*sqr(x+1)%mod;}
namespace IO{
#define getchar() (tt == ss && (tt = (ss = In) + fread(In, 1, 110000000, stdin), ss == tt) ? EOF : *ss++)
char In[110000000], *ss=In, *tt=In;//In数组要根据输入量更改大小
const int END = 2147483647;//忽略量
//整数读入
inline n_ rd(){//修改一下变量类型即可(int\ll\ul\ui)
n_ x=0;int fg=1;
char c=getchar();
while(c==' ' || c=='\n')c=getchar();
if(c=='-')fg=-1,c=getchar();
while(isdigit(c)){
x=(x<<3)+(x<<1)+(c-48);
c=getchar();
}
return x*fg;
}
//字符串读入
inline int rds(char *s){
register int len=0;
register char c=getchar();
while(c==' ' || c=='\n' || c=='\r')c=getchar();
while(c!=' ' && c!='\n' && c!='\r' && c!='EOF'){
s[len++]=c;
c=getchar();
}
return len;
}
//读入一行字符串
inline int getline(char *s){
register int len=0;
register char c=getchar();
while(c==' ' || c=='\n')c=getchar();
while(c!='\n' && c!='EOF'){
s[len++]=c;
c=getchar();
}
return len;
}
//整数输出
inline void wr(register n_ x){//不加换行符
if(x<0)putchar('-'),x=-x;
if(x>=10)wr(x/10);
putchar(x%10+'0');
}
inline void wrn(register n_ x){//加换行符
wr(x);
putchar('\n');
}
//正整数格式化输出
inline void wrd(register n_ x,register int d){//不加换行符
if(!x){putchar('0');return;}
register n_ xx =x;
while(xx)d--,xx/=10;
FOR(i,0,d)putchar('0');
wr(x);
}
inline void wrdn(register n_ x,register int d){//加换行符
wrd(x,d);
putchar('\n');
}
//字符串输出
inline void wrs(const char *s){//不输出换行符
for(register int i=0;s[i];++i)putchar(s[i]);
}
inline void wrsn(const char *s){//输出换行符
wrs(s);
putchar('\n');
}
inline void debug(const char *s,n_ a=END,n_ b=END,n_ c=END,n_ d=END,n_ e=END,n_ f=END){
if(s!=NULL)wrs(s),putchar(' ');
if(a!=END)wr(a),putchar(' ');
if(b!=END)wr(b),putchar(' ');
if(c!=END)wr(c),putchar(' ');
if(d!=END)wr(d),putchar(' ');
if(e!=END)wr(e),putchar(' ');
if(f!=END)wr(f),putchar(' ');
putchar('\n');
}
}
using namespace IO;
char a[maxn][maxn][102];
int mp[27][27],deg[30],vis[30],len[maxn][maxn],hv[maxn];
vector<int>g[30];
queue<int>q;
int main(){
int n=rd(),k=rd();
for(int i=1;i<=n;++i){
int p=rd();
hv[p]=1;
for(int j=0;j<k;++j){
len[p][j]=rds(a[p][j]);
}
}
int lasti=-1,lastj=-1;
for(int i=0;i<maxn;++i){
if(!hv[i])continue;
for(int j=0;j<k;++j){
int c=-1;
for(int h=0;h<len[i][j];++h){
vis[a[i][j][h]-'a']=1;
if(lasti!=-1 && h<len[lasti][lastj] && c==-1 && a[i][j][h]!=a[lasti][lastj][h]){
c=h;
}
}
if(c!=-1){
int v=a[i][j][c]-'a'+1,u=a[lasti][lastj][c]-'a'+1;
if(!mp[u][v])g[u].push_back(v),deg[v]++;
mp[u][v]=1;
if(mp[v][u]){
return printf("IMPOSSIBLE\n"),0;
}
}else if(lasti!=-1 && len[lasti][lastj]>len[i][j])return printf("IMPOSSIBLE\n"),0;
lasti=i,lastj=j;
}
}
int tot=0;
for(int i=1;i<=26;++i){
if(!vis[i-1])continue;
if(!deg[i])q.push(i);
tot++;
}
vector<int>ans;
while(!q.empty()){
int u=q.front();q.pop();
ans.push_back(u-1);
for(auto v:g[u]){
deg[v]--;
if(!deg[v])q.push(v);
}
}
if(ans.size()<tot)return printf("IMPOSSIBLE\n"),0;
for(int i=0;i<ans.size();++i)printf("%c",ans[i]+'a');puts("");
}1365. How Many Numbers Are Smaller Than the Current Number | 771. Jewels and Stones |
1512. Number of Good Pairs | 672. Richest Customer Wealth |
1470. Shuffle the Array | 1431. Kids With the Greatest Number of Candies |
1480. Running Sum of 1d Array | 682. Baseball Game |
496. Next Greater Element I | 232. Implement Queue using Stacks |
844. Backspace String Compare | 20. Valid Parentheses |
746. Min Cost Climbing Stairs | 392. Is Subsequence |
70. Climbing Stairs | 53. Maximum Subarray |
1527A. And Then There Were K | 1689. Partitioning Into Minimum Number Of Deci-Binary Numbers |
318. Maximum Product of Word Lengths | 448. Find All Numbers Disappeared in an Array |
1155. Number of Dice Rolls With Target Sum | 415. Add Strings |
22. Generate Parentheses | 13. Roman to Integer |
2. Add Two Numbers | 515. Find Largest Value in Each Tree Row |
345. Reverse Vowels of a String | 628. Maximum Product of Three Numbers |
1526A - Mean Inequality | 1526B - I Hate 1111 |